package com.demo.java.OD301_350.OD344;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【人气最高的店铺(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146159522
 */
public class OdMain {
    // 用来存储商店的受欢迎度
    public static Map<Integer, Integer> popularityMap = new HashMap<>();

    // 记录当前最小的金钱花费
    public static int minMoney = Integer.MAX_VALUE;

    // 用来存储当前的花费金额
    public static int money;

    public static void main(String[] args) {
        // 创建扫描器以读取输入
        Scanner scanner = new Scanner(System.in);

        // 读取输入的第一行并分割成商店数量和投票数量
        String[] input1 = scanner.nextLine().split(",");
        int shopCount = Integer.parseInt(input1[0]);  // 商店数量
        int voteCount = Integer.parseInt(input1[1]);  // 投票数量

        // 存储每个人投票的商店和受欢迎度
        List<int[]> peopleList = new ArrayList<>();

        // 将商店1的初始受欢迎度设为0
        popularityMap.put(1, 0);

        // 读取每个商店的编号和受欢迎度
        for (int i = 0; i < shopCount; i++) {
            String[] input2 = scanner.nextLine().split(",");
            int shop = Integer.parseInt(input2[0]);  // 商店编号
            int popularity = Integer.parseInt(input2[1]);  // 受欢迎度

            // 如果商店不是1，记录下投票情况
            if (shop != 1) {
                peopleList.add(new int[]{shop, popularity});
            }

            // 更新每个商店的投票人数
            popularityMap.put(shop, popularityMap.getOrDefault(shop, 0) + 1);
        }

        // 处理投票
        processVotes(peopleList, new ArrayList<>(), 0);

        // 输出最小花费的金额
        System.out.println(minMoney);
    }

    // 递归处理投票
    public static void processVotes(List<int[]> peopleList, List<int[]> changeList, int index) {
        // 如果当前的投票选择能够使商店1成为最受欢迎的商店并且花费小于当前最小值
        if (isMax(changeList) && minMoney > money) {
            // 更新最小花费
            minMoney = money;
        } else {
            // 遍历所有可能的投票组合
            for (int i = index; i < peopleList.size(); i++) {
                // 将当前商店的投票添加到变动列表中
                changeList.add(peopleList.get(i));

                // 递归处理下一个投票组合
                processVotes(peopleList, changeList, i + 1);

                // 回溯，移除最后一个添加的投票
                changeList.remove(changeList.size() - 1);
            }
        }
    }

    // 判断是否已经达到商店1受欢迎度最大且其他商店无可能超过它
    public static boolean isMax(List<int[]> changeList) {
        // 创建一个临时的受欢迎度映射，记录修改后的商店受欢迎度
        Map<Integer, Integer> tempMap = new HashMap<>(popularityMap);

        // 重置花费
        money = 0;

        // 遍历所有被选中的投票，将受欢迎度更新并增加花费
        for (int[] ints : changeList) {
            int shop = ints[0];  // 商店编号
            money += ints[1];  // 增加当前商店的花费
            tempMap.put(shop, tempMap.get(shop) - 1);  // 更新该商店的投票人数
            tempMap.put(1, tempMap.get(1) + 1);  // 商店1的投票人数加1
        }

        // 将受欢迎度映射转为列表并按受欢迎度从高到低排序
        List<Map.Entry<Integer, Integer>> entryList = new ArrayList<>(tempMap.entrySet());
        entryList.sort((a, b) -> b.getValue() - a.getValue());

        // 获取最受欢迎的商店
        int firstShop = entryList.get(0).getKey();

        // 如果商店1是最受欢迎的并且它的受欢迎度高于其他商店，则返回 true
        if (firstShop == 1 && (entryList.size() == 1 || entryList.get(0).getValue() > entryList.get(1).getValue())) {
            return true;
        }

        // 否则返回 false
        return false;
    }
}